\subsection{An $O(\min\{n\sqrt{k\log n}, nk\})$ round algorithm}
\label{sec:upper}
Our algorithm is given in Algorithm~\ref{alg:flow_based} and analyzed
in Lemma~\ref{lem:level.flow} and~\ref{thm:flow_based}.

\begin{lemma}
\label{lem:level.flow}
Let there be $k \leq n$ tokens at given source nodes and let $v$ be an
arbitrary node. Then, all the tokens can be sent to $v$ using
broadcasts in $O(n)$ rounds.
\end{lemma}
\begin{proof}
By lemma~\ref{lem:level.steiner}, we will be done in $n + k$ rounds if
we can show that $k$ paths, one from every source vertex at level $0$
to $v_{2(n+k)}$, can be packed in the corresponding evolution graph
with $2(n+k) + 1$ levels respecting the edge capacities. For this, we
consider the evolution graph and add to it a special vertex $v_{-1}$
at level $-1$ and connect it to every source at level $0$ by an edge
of capacity 1. (Multiple edges get fused with corresponding increase
in capacity if multiple tokens have the same source.) We claim that
the value of the min-cut between $v_{-1}$ and $v_{2(n+k)}$ is at least
$k$. Before proving this, we complete the proof of the claim assuming
this.  By the max flow min cut theorem, the max flow between $v_{-1}$
and $v_{2(n+k)}$ is at least $k$. Since we connected $v_{-1}$ with
each of the $k$ token sources at level $0$ by a unit capacity edge, it
follows that unit flow can be routed from each of these sources at
level $0$ to $v_{2(n+k)}$ respecting the edge capacities. It is easy
to see that this implies we can pack $k$ paths, one from every source
vertex at level $0$ to $v_{2(n+k)}$, respecting the edge capacities.

To prove our claimed bound on the min cut, consider any cut of the
evolution graph separating $v_{-1}$ from $v_{2(n+k)}$ and let $S$ be
the set of the cut containing $v_{-1}$. If $S$ includes no vertex from
level $0$, we are immediately done. Otherwise, observe that if $v_{2j}
\in S$ for some $0 \leq j < (n+k)$ and $v_{2(j+1)} \notin S$, then the
value of the cut is infinite as it cuts the buffer edge of infinite
capacity out of $v_{2j}$. Thus we may assume that if $v_{2j} \in S$,
then $v_{2(j+1)} \in S$. Also observe that since each of the
communication graphs $G_1, \ldots, G_{n+k}$ are connected, if the
number of vertices in $S$ from level $2(j+1)$ is no more than the
number of vertices from level $2j$ and not all vertices from level
$2(j+1)$ are in $S$, we get at least a contribution of $1$ in the
value of the cut. But since the total number of nodes is $n$ and
$v_{2(n+k)} \notin S$, there must be at least $k$ such levels, which
proves the claim.
\end{proof}

\begin{algorithm}[ht!]
\caption{$O(\min\{n \sqrt{k\log n}, nk\})$ round algorithm in the
  offline model}
\label{alg:flow_based}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_i$, $i = 1, 2, \ldots$
  \ENSURE Schedule to disseminate $k$ tokens.

  \medskip

  \IF{$k \leq \sqrt{\log n}$}

  \FOR{each token $t$} \label{alg.step:flow_based.trivial}

  \STATE For the next $n$ rounds, let every node who has token
  $t$ broadcast the token.

  \ENDFOR 

  \ELSE

  \STATE Choose a set $S$ of $2\sqrt{k \log n}$ random nodes. \label{alg.step:random}
  
  \FOR{each vertex in $v \in S$} \label{alg.step:flow_based.phase_1}

  \STATE Send each of the $k$ tokens to vertex $v$ in $O(n)$ rounds. 

  \ENDFOR

  \FOR{each token $t$} \label{alg.step:flow_based.phase_2}

  \STATE For the next $2n \sqrt{(\log n)/k}$ rounds, let every node who has token
  $t$ broadcast the token.

  \ENDFOR

  \ENDIF

\end{algorithmic}
\end{algorithm}

\begin{theorem}
\label{thm:flow_based}
Algorithm~\ref{alg:flow_based} solves the $k$-gossip problem using
$O(\min\{n \sqrt{k \log n}, nk\})$ rounds with high probability in
the offline model.
\end{theorem}
\begin{proof}
It is trivial to see that if $k \leq \sqrt{\log n}$, then the
algorithm will end in $nk$ rounds and each node receives all the $k$
tokens. Assume $k > \sqrt{\log n}$. By Lemma~\ref{lem:level.flow}, all
the tokens can be sent to all the nodes in $S$ using $O(n \sqrt{k \log
  n})$ rounds. Now fix a node $v$ and a token $t$. Since token $t$ is
broadcast for $2n \sqrt{(\log n)/k}$ rounds, there is a set $S^t_v$ of
at least $2n \sqrt{(\log n)/k}$ nodes from which $v$ is reachable
within those rounds.  It is clear that if $S$ intersects $S^t_v$, $v$
will receive token $t$. Since the set $S$ was picked uniformly at
random, the probability that $S$ does not intersect $S^t_v$ is at most
\[ \frac{{n - 2n\sqrt{(\log n)/k} \choose 2\sqrt{k \log n}}}{{n \choose 2\sqrt{k \log n}}} < \left(\frac{n - 2n\sqrt{(\log n)/k}}{n}\right)^{2\sqrt{k \log n}} \le \frac{1}{n^4}. \] 
Thus every node receives every token with probability $1-1/n^3$. It is
also clear that the algorithm finishes in $O(n \sqrt{k \log n})$
rounds.
\end{proof}

Algorithm~\ref{alg:flow_based} can be derandomized using the standard
technique of conditional expectations, shown in
Algorithm~\ref{alg:derandomize}. Given a sequence of communication
graphs, if node $u$ broadcasts token $t$ for $\Delta$ rounds and every
node that receives token $t$ also broadcasts $t$ during that period,
then we say node $v$ is within $\Delta$ {\em broadcast distance} to
$u$ if and only if $v$ receives token $t$ by the end of round
$\Delta$. Let $S$ be a set of nodes, and $|S|\le 2 \sqrt{k \log
  n}$. We use $\dprob{u}{S}{T}$ to denote the probability that the
broadcast distance from node $u$ to set $X$ is greater than $2n
\sqrt{(\log n)/k}$, where $X=S\cup \cub{\mbox{pick }2\sqrt{k\log n} -
  |S|\mbox{ nodes uniformly at random from }V\setminus T}$, and
$\dsumprob{S}{T}$ denotes the sum, over all $u$ in $V$, of
$\dprob{u}{S}{T}$.

\begin{algorithm}[ht!]
\caption{Derandomized algorithm for Step~\ref{alg.step:random} in
  Algorithm~\ref{alg:flow_based}}
\label{alg:derandomize}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_i$, $i = 1, 2,
  \ldots$, and $k \ge \sqrt{\log n}$

  \ENSURE A set of $2\sqrt{k\log n}$ nodes $S$ such that the broadcast
  distance from every node $u$ to $S$ is within $2 n\sqrt{(\log
    n)/k}$.
  \medskip

  \STATE Set $S$ and $T$ be $\emptyset$.

  \FOR{each $v\in V$}

  \STATE $T = T \cup \{v\}$
  
  \IF{$\dsumprob{S \cup \{v\}}{T} \le \dsumprob{S}{T}$ \label{alg.step:cal}}

  \STATE $S = S\cup \{v\}$

%  \STATE Calculate $p=\dprob{V}{S \cup \{v\}}$. 
  
%  \IF{$p \ge 1- \frac{1}{n^3}$}

  \ENDIF

  \ENDFOR

  \RETURN $S$

\end{algorithmic}
\end{algorithm}

\begin{lemma}
The set $S$ returned by Algorithm~\ref{alg:derandomize} contains at
most $2\sqrt{k\log n}$ nodes, and the broadcast distance from every
node to $S$ is at most $2n\sqrt{(\log n)/k}$.
\end{lemma}
\begin{proof}
Let us view the process of randomly selecting $2\sqrt{k\log n}$ nodes
as a computation tree. This tree is a complete binary tree of height
$n$. There are $n+1$ nodes on any root-leaf path. The level of a node
is its distance from the root. The computation starts from the
root. Each node at the $i$th level is labeled by $b_i \in \{0,1\}$,
where 0 means not including node $i$ in the final set and 1 means
including node $i$ in the set. Thus, each root-leaf path, $b_1b_2\dots
b_n$, corresponds to a selection of nodes.  For a node $a$ in the
tree, let $S_a$ (resp., $T_a$) denote the sets of nodes that are
included (resp., lie) in the path from root to $a$.

By Theorem~\ref{thm:flow_based}, we know that for the root node $r$,
we have $\dsumprob{\emptyset}{S_r} =\dsumprob{\emptyset}{\emptyset}\le
1/n^3$.  If $c$ and $d$ are the children of $a$, then $T_c$ = $T_d$,
and there exists a real $0 \le p \le 1$ such that for each $u$ in $V$,
$\dprob{u}{S_a}{T_a}$ equals $p \dprob{u}{S_c}{T_c} +
(1-p)\dprob{u}{S_d}{T_d}$.  Therefore, $\dsumprob{S_a}{T_a}$ equals $p
\dsumprob{S_c}{T_c} + (1-p) \dsumprob{S_d}{T_d}$.  We thus obtain that
$\min\{\dsumprob{S_c}{T_c},\dsumprob{S_d}{T_d}\} \le
\dsumprob{S_a}{T_a}$.  Since we set $S$ to be $X$ in $\{S_c, S_d\}$
that minimizes $\dsumprob{X}{T_c}$, we maintain the invariant that
$\dsumprob{S}{T} \le 1/n^3$.  In particular, when the algorithm
reaches a leaf $l$, we know $\dsumprob{S_l}{V}\le 1/n^3$.  But a leaf
$l$ corresponds to a complete node selection, so that
$\dprob{u}{S_l}{V}$ is 0 or 1 for all $u$, and hence
$\dsumprob{S_l}{V}$ is an integer.  We thus have $\dsumprob{S_l}{V} =
0$, implying that the broadcast distance from node $u$ to set $S_l$ is
at most $2n \sqrt{(\log n)/k}$ for every $l$.  Furthermore, $|S_l|$ is
$2 k \sqrt{\log n}$ by construction.

Finally, note that Step~\ref{alg.step:cal} of
Algorithm~\ref{alg:derandomize} can be implemented in polynomial time,
since for each $u$ in $V$, $\dprob{u}{S}{T}$ is simply the ratio of
two binomial coefficients with a polynomial number of bits.  Thus,
Algorithm~\ref{alg:derandomize} is a polynomial time algorithm with
the desired property.
\end{proof}
